//下降路径最小和
//测试链接：https://leetcode.cn/problems/minimum-falling-path-sum/
public class MinFallingPathSum {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;

        int[][] dp = new int [m+2][n+2];
        for(int i = 1; i < m+1; i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n+1] = Integer.MAX_VALUE;
        }


        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                //找到当前节点上对应上面相邻的三个位置的最小值
                int temp = Math.min(dp[i-1][j-1], dp[i-1][j]);
                int min = Math.min(dp[i-1][j+1], temp);

                dp[i][j] = min+matrix[i-1][j-1];
            }
        }

        int ans = dp[m][1];
        for(int i = 1; i <= n; i++) {
            ans = Math.min(ans, dp[m][i]);
        }
        return ans;
    }
}
